/**
 * 剑指 Offer 36. 二叉搜索树与双向链表
 * https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
 */

/**
 * @param {TreeNode} root
 * @return {TreeNode[]}
 */
function dfs(root) {
  if (!root.left && !root.right) {
    return [root, root];
  }
  let head = root;
  if (root.left) {
    const [leftHead, leftTail] = dfs(root.left);
    head = leftHead;
    leftTail.right = root;
    root.left = leftTail;
  }
  let tail = root;
  if (root.right) {
    const [rightHead, rightTail] = dfs(root.right);
    tail = rightTail;
    root.right = rightHead;
    rightHead.left = root;
  }
  return [head, tail];
}

/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
function treeToDoublyList(root) {
  if (!root) {
    return null;
  }
  const [head, tail] = dfs(root);
  tail.right = head;
  head.left = tail;
  return head;
}

console.log(treeToDoublyList(null));
